Conceitos Básicos

Tópicos

1. Definições e Exemplos
   1. Arestas
   2. Graus
      1. Definição de grau
      2. Grau de Entrada ou Saída
      3. Soma dos graus
   3. Ordem, Tamanho e Rótulo
   4. Direcionado ou Orientado
2. Teoremas
   1. Teorema 1

• Notações:
  • G: Grafo com conjunto de vértices V(G) e conjunto de arestas E(G).
  • n: Número de vértices de G.
  • m: Número de arestas de G.

Definições e Exemplos

Arestas

• Incidentes: Os extremos de uma aresta são ditos incidentes com a aresta
• Adjacentes: Dois vértices que são incidentes a uma mesma aresta são ditos adjacentes.

• Loop (LAÇO): uma aresta com extremos idênticos.
  

• Link (enlace): aresta com extremos diferentes.
  

• Arestas Múltiplas: mais de uma aresta com os mesmos extremos.
  

• Arestas paralelas: duas arestas com os mesmos extremos.
  

Graus

Definição de grau

• Definição: O grau de um vértice v, denotado por d(v), é o número de arestas incidentes a esse vértice v .
  • Grafos com apenas um vértice são ditos triviais.
  • Um grafo é simples se não possuir laços e arestas múltiplas.
• Obs: Um laço conta 2 vezes na função de grau.
  

• A sequência de grau de um grafo consiste em que os graus são escritos em ordem crescente.

1. Sequência de grau do grafo (i): (1, 1, 2, 2, 2)
2. Sequência de grau do grafo (ii): (1, 1, 2, 2, 2)
3. Sequência de grau do grafo (iii): (1, 3, 6, 8)

Grau de Entrada ou Saída

• Grau de entrada: o vértice é denotado d⁻(v)⁺.
  • O vértice é chamado de fonte (é a origem de suas arestas incidentes).
• Grau de saída: o vértice é denotado d⁺(v).
  • O vértice é chamado de sumidouro.

Soma dos graus

• O grafo é chamado de dígrafo balanceado se:

• Exemplo:
  

Ordem, Tamanho e Rótulo

• Um grafo é dito rotulado se existem atribuições associadas a suas arestas ou vértices
• Denomina-se ordem de G a cardinalidade do seu conjunto de vértices. |V|= n.
• Denomina-se tamanho de G a cardinalidade do seu conjunto de arestas. |E|= m.
  

Grafo (1) ordem 5 e tamanho 8 .
Grafo (2) ordem 4 e tamanho 4 .

Direcionado ou Orientado

Definição: Um grafo é dito direcionado ou orientado ou, simplesmente, dígrafo quando o sentido das ligações entre os vértices é importante. Nesse caso, as arestas possuem um sentido marcado por uma seta e recebem o nome de arcos.

flowchart LR

a --> b
b --> a
a --> c
c--> d
d--->b
c-->e
e-->a

Teoremas

Teorema 1

• Em qualquer grafo, a soma dos graus de um grafo G = (V; E) é igual a duas vezes o número de arestas

• Exemplo: Um grafo tem exatamente 4 vértices, cada um de grau 3. Quantas arestas este grafo tem?